#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef unsigned long long LL;
const int MAXN = 1e6+23;
int fib[MAXN];
int Kuai_POW(LL a, LL b, LL m) {
	LL ret = 1;
	a=a%m;
	while (b) {
		if (b&1) {
			ret = (ret * a) % m;
		}
		a = (a*a) % m;
		b = (b>>1);
	}
	return ret;
}
int main(int argc, char** argv) {
	#ifdef hai
	freopen("in.txt", "r", stdin);
	#endif
	int T;
	LL a,b,k;
	cin>>T;
	while (T--) {
		cin>>a>>b>>k;
		if (k==1) {
			printf("0\n");
			continue;	
		}
		int len = k*k+7;
		fib[0]=0; fib[1]=1;
		int m;
		for (int i=2; i<len; ++i) {
			fib[i] = (fib[i-1] + fib[i-2]) % k;
			if (fib[i]==1 && fib[i-1]==0) {
				m=i-1;
				break;
			}
		}
//		printf("check: %llu %llu %d\n", a, b, m);
		printf("%d\n", fib[Kuai_POW(a,b,m)]);
	}
	return 0;
}
